#include "mySearch.h"

// SSTable类：表示顺序查找表（有序数组）
SSTable::SSTable()
{
    length = 0;            // 初始化顺序表的长度为0
    origin = nullptr;      // 初始化顺序表的数据指针为nullptr
}

// SSTable类的构造函数：通过给定数据初始化顺序表
SSTable::SSTable(int _length, int* data)
{
    length = _length;      // 设置顺序表的长度
    origin = new int[length];   // 为数据数组分配内存
    for (int i = 0; i < length; i++)  // 将数据数组中的元素赋值给顺序表的origin
    {
        origin[i] = data[i];
    }
}

// SSTable类的析构函数：释放顺序表的数据内存
SSTable::~SSTable()
{
    if (origin)
    {
        delete[] origin;   // 删除数据数组
        origin = nullptr;   // 防止悬空指针
    }
}

// 获取顺序表的长度
int SSTable::getLength()
{
    return length;
}

// 获取顺序表的数据指针
int* SSTable::getOrigin()
{
    return origin;
}

// 设置顺序表的长度
void SSTable::setLength(int _length)
{
    length = _length;
}

// 设置顺序表的数据
void SSTable::setOrigin(int* data)
{
    origin = data;
}

// 二分查找：在顺序表中查找值为val的元素
int SSTable::binSearch(int val)
{
    int low = 0, high = length - 1;  // 定义查找的范围
    while (low <= high)  // 循环直到找到元素或范围为空
    {
        int mid = (low + high) / 2;   // 计算中间位置
        if (origin[mid] == val)       // 如果中间值等于目标值
        {
            return mid;  // 返回索引
        }
        else if (origin[mid] < val)   // 如果中间值小于目标值
        {
            low = mid + 1;  // 调整低位索引
        }
        else  // 如果中间值大于目标值
        {
            high = mid - 1;  // 调整高位索引
        }
    }
    return -1;  // 如果没找到，返回-1
}

// BSTreeNode类：二叉搜索树节点类
BSTreeNode::BSTreeNode()
{
    data = 0;            // 初始化数据为0
    lchild = nullptr;    // 初始化左子节点为nullptr
    rchild = nullptr;    // 初始化右子节点为nullptr
}

// BSTreeNode类的构造函数：通过给定的数据初始化节点
BSTreeNode::BSTreeNode(int _data)
{
    data = _data;        // 设置节点的数据
    lchild = nullptr;    // 左子节点为nullptr
    rchild = nullptr;    // 右子节点为nullptr
}

// BSTreeNode类的构造函数：通过给定的数据和左右子节点初始化节点
BSTreeNode::BSTreeNode(int _data, BSTreeNode* _lchild, BSTreeNode* _rchild)
{
    data = _data;        // 设置节点的数据
    lchild = _lchild;    // 设置左子节点
    rchild = _rchild;    // 设置右子节点
}

// BSTreeNode类的析构函数：递归删除左右子节点
BSTreeNode::~BSTreeNode()
{
    if (lchild)
    {
        delete lchild;   // 删除左子节点
        lchild = nullptr; // 防止悬空指针
    }
    if (rchild)
    {
        delete rchild;   // 删除右子节点
        rchild = nullptr; // 防止悬空指针
    }
}

// 获取节点的数据
int BSTreeNode::getData()
{
    return data;
}

// 设置节点的数据
void BSTreeNode::setData(int _data)
{
    data = _data;
}

// 获取左子节点
BSTreeNode* BSTreeNode::getLChild()
{
    return lchild;
}

// 设置左子节点
void BSTreeNode::setLChild(BSTreeNode* _lchild)
{
    lchild = _lchild;
}

// 获取右子节点
BSTreeNode* BSTreeNode::getRChild()
{
    return rchild;
}

// 设置右子节点
void BSTreeNode::setRChild(BSTreeNode* _rchild)
{
    rchild = _rchild;
}

// BSTree类：表示二叉搜索树
BSTree::BSTree()
{
    num = 0;       // 初始化节点数为0
    root = nullptr; // 初始化根节点为nullptr
}

// BSTree类的构造函数：通过给定的数据数组初始化二叉搜索树
BSTree::BSTree(int _num, int* data)
{
    num = _num;  // 设置树中节点的数量
    root = new BSTreeNode(data[0]);  // 将第一个数据作为根节点
    for (int i = 1; i < num; i++)  // 对剩余的数据构建树
    {
        BSTreeNode* p = root;
        while (true)  // 查找插入位置
        {
            if (data[i] < p->getData())  // 如果数据小于当前节点数据，往左子树插入
            {
                if (p->getLChild() != nullptr)
                {
                    p = p->getLChild();  // 继续在左子树查找
                }
                else
                {
                    p->setLChild(new BSTreeNode(data[i]));  // 在左子树插入新节点
                    break;
                }
            }
            else if (data[i] > p->getData())  // 如果数据大于当前节点数据，往右子树插入
            {
                if (p->getRChild() != nullptr)
                {
                    p = p->getRChild();  // 继续在右子树查找
                }
                else
                {
                    p->setRChild(new BSTreeNode(data[i]));  // 在右子树插入新节点
                    break;
                }
            }
            else  // 如果数据已经存在，不插入
            {
                break;
            }
        }
    }
}

// BSTree类的析构函数：删除树中的所有节点
BSTree::~BSTree()
{
    if (root)
    {
        delete root;   // 删除根节点，递归删除所有子节点
        root = nullptr; // 防止悬空指针
    }
}

// 获取树中节点的数量
int BSTree::getNum()
{
    return num;
}

// 设置树中节点的数量
void BSTree::setNum(int _num)
{
    num = _num;
}

// 获取根节点
BSTreeNode* BSTree::getRoot()
{
    return root;
}

// 设置根节点
void BSTree::setRoot(BSTreeNode* _root)
{
    root = _root;
}

// 遍历打印树：前序遍历，将结果存储在result中
void printTemp(BSTreeNode* root, string& result)
{
    if (root == nullptr)
    {
        return;
    }
    result += to_string(root->getData()) + " "; // 访问当前节点
    printTemp(root->getLChild(), result); // 遍历左子树
    printTemp(root->getRChild(), result); // 遍历右子树
}

// 打印二叉搜索树的前序遍历结果
string BSTree::printTree()
{
    string result;
    printTemp(root, result); // 递归打印树的前序遍历
    return result;
}

// 查找树中是否存在某个节点
bool BSTree::searchNode(int val) 
{
    BSTreeNode* p = root;
    while (p != nullptr)
    {
        if (val == p->getData())  // 如果找到节点
        {
            return true;
        }
        else if (val < p->getData())  // 如果目标值小于当前节点，查找左子树
        {
            p = p->getLChild();
        }
        else  // 如果目标值大于当前节点，查找右子树
        {
            p = p->getRChild();
        }
    }
    return false;  // 如果没有找到节点
}

bool BSTree::addNode(int val)
{
    if (root == nullptr)
    {
        root = new BSTreeNode(val);
        num++;
        return true;
    }
    BSTreeNode* p = root;
    while (true)
    {
        if (val < p->getData())
        {
            if (p->getLChild() != nullptr)
            {
                p = p->getLChild();
            }
            else
            {
                p->setLChild(new BSTreeNode(val));
                num++;
                return true;
            }
        }
        else if (val > p->getData())
        {
            if (p->getRChild() != nullptr)
            {
                p = p->getRChild();
            }
            else
            {
                p->setRChild(new BSTreeNode(val));
                num++;
                return true;
            }
        }
        else
        {
            return false;
        }
    }
}

bool BSTree::deleteNode(int val)
{
    // 找到节点p、父节点fa
    BSTreeNode* p = root;
    BSTreeNode* fa = nullptr;
    while (p != nullptr && p->getData() != val)
    {
        fa = p;
        if (val < p->getData())
        {
            p = p->getLChild();
        }
        else
        {
            p = p->getRChild();
        }
    }
    if (p == nullptr)
    {
        // 没有找到要删除的节点
        return false;
    }
    // 节点p有两个子节点，用其右子树的最小数据代替p的数据并递归删除右子树的最小数据
    if (p->getLChild() != nullptr && p->getRChild() != nullptr)
    {
        BSTreeNode* t = p->getRChild();
        while (t->getLChild() != nullptr)
        {
            fa = t;
            t = t->getLChild();
        }
        // 用右子树的最小数据代替p的数据
        p->setData(t->getData());
        // p指向要删除的节点，fa指向p的父节点
        val = t->getData();
        p = t;
    }
    // 节点p有一个或没有子节点
    BSTreeNode* child = nullptr;
    if (p->getLChild() != nullptr)
    {
        child = p->getLChild();
    }
    else if (p->getRChild() != nullptr)
    {
        child = p->getRChild();
    }
    if (fa == nullptr)
    {
        root = child;
    }
    else if (fa->getLChild() == p)
    {
        fa->setLChild(child);
    }
    else
    {
        fa->setRChild(child);
    }
    delete p;
    num--;
    return true;
}

